/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/paint-fence
   @Language: C++
   @Datetime: 19-04-22 11:52
   */

class Solution {
public:
	/**
	 * @param n: non-negative integer, n posts
	 * @param k: non-negative integer, k colors
	 * @return: an integer, the total number of ways
	 */
	int numWays(int n, int k) {
		// write your code here
		int a=k, b=k*k, c;
		while(--n){
			c=(k-1)*(a+b);
			a=b;
			b=c;
		}
		return a;
	}
};
